package th.android.sudoku;

import java.util.*;

public class SudoHelper {

    static final int N = 9;

    private int count;
    private boolean[][] line = new boolean[9][9];
    private boolean[][] column = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    private boolean valid = false;
    private List<int[]> spaces = new ArrayList<int[]>();

    private int[][] origin = new int[9][9];
    private List<int[][]> mSolutions = new LinkedList<>();

    public List<int[][]> getAllSolution(int[][] arr) {
        mSolutions.clear();
        initOrigin(arr);
        solveSudoku(Integer.MAX_VALUE);
        return mSolutions;
    }

    public List<int[][]> getAllSolution(int[] arr) {
        mSolutions.clear();
        initOrigin(arr);
        solveSudoku(Integer.MAX_VALUE);
        return mSolutions;
    }

    public List<int[][]> getTwoSolutions(int[][] arr) {
        mSolutions.clear();
        initOrigin(arr);
        solveSudoku(2);
        return mSolutions;
    }

    public void solveSudoku(int maxSolution) {
        reset();
        dfs(0, maxSolution);
    }

    public void dfs(int pos, int maxSolution) {
        if (pos == spaces.size()) {
            count++;
            int[][] solution = new int[N][N];
            for (int i = 0; i < N; i++) {
                System.arraycopy(origin[i], 0, solution[i], 0, N);
            }
            mSolutions.add(solution);
            return;
        }
        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && count < maxSolution; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                origin[i][j] = digit + 1;
                dfs(pos + 1, maxSolution);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
                origin[i][j] = 0;
            }
        }
    }

    private void initOrigin(int[][] arr) {
        for (int i = 0; i < N; i++) {
            System.arraycopy(arr[i], 0, origin[i], 0, N);
        }
    }

    private void initOrigin(int[] arr) {
        for (int i = 0; i < N; i++) {
            System.arraycopy(arr, i * N, origin[i], 0, 9);
        }
    }

    private void reset() {
        spaces.clear();
        count = 0;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (origin[i][j] == 0) {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = origin[i][j] - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
    }

    public HashMap<Cell, Integer> printFreedom(int[][] arr) {
        int[] lineTags = new int[N];
        int[] columnTags = new int[N];
        int[] boxTags = new int[N];
        Arrays.fill(lineTags, 0x1ff);
        Arrays.fill(columnTags, 0x1ff);
        Arrays.fill(boxTags, 0x1ff);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] != 0) {
                    int index = arr[i][j] - 1;
                    int boxIndex = i / 3 * 3 + j / 3;
                    lineTags[i] &= (~(1 << index));
                    columnTags[j] &= (~(1 << index));
                    boxTags[boxIndex] &= (~(1 << index));
                }
            }
        }
        HashMap<Cell, Integer> freedom = new HashMap<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 0) {
                    int boxIndex = i / 3 * 3 + j / 3;
                    int tag = lineTags[i] & columnTags[j] & boxTags[boxIndex];
                    freedom.put(new Cell(i, j), Integer.bitCount(tag));
                }
            }
        }
        return freedom;
    }
}
